// 给定一个整数数组nums，设计算法来打乱一个没有重复元素的数组，打乱后，数组的所有排列应该是等可能的
// 实现Solution 类，使用整数数组nums初始化对象
// reset，重设数组到它的初始状态并返回
// shuffle，返回数组随机打乱后的结果

// 思路：洗牌算法，长度为n的数组中，每个位置的选择其概率都是相同的
// 位置i，从 剩余 n - i 个数中选择任意一个与位置i交换位置，其概率都是相同的
// 时间复杂度：O(n)
// 空间复杂度：O(n)

class Solution {
    constructor(nums) {
        this.nums = nums
    }
    reset () {
        return this.nums
    }
    shuffle() {
        const shuffleNums = [...this.nums]
        for (let i = 0; i < shuffleNums.length; i++) {
            // 注意这里随机索引的计算
            const randomIndex = Math.floor(Math.random() * (shuffleNums.length - i)) + i;
            [shuffleNums[i], shuffleNums[randomIndex]] = [shuffleNums[randomIndex], shuffleNums[i]];            
        }
        return shuffleNums
    }

}

let arr = [1,2,3,4,5]
let solution = new Solution(arr)
console.log(solution.shuffle());
console.log(solution.reset());